package mao.leetcode.others;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

class Solution {
    public static void main(String[] args) {
     generateParenthesis(5);
        countAndSay(4);
        lengthOfLastWord("  aaaaaa   bbbbb  ");
        System.out.println("4444");

    }
    public static int lengthOfLastWord(String s) {
        if (s.charAt(s.length()-1) == ' ') return 0;
        String[] s1 = s.split(" ");
        return s1[s1.length-1].length();


    }

    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int maxSubstrEndByCurrentIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxSubstrEndByCurrentIndex+nums[i] > nums[i]){
                maxSubstrEndByCurrentIndex+=nums[i];
            }else {
                maxSubstrEndByCurrentIndex=nums[i];
            }
            ans = Math.max(ans,maxSubstrEndByCurrentIndex);
        }
        return ans;
    }


    public static String countAndSay(int n) {
        if (n == 1) return "1";
        StringBuilder builder = new StringBuilder();
        String ans = new String("1");
        char currentChar;
        int count = 0;
        for (int i = 2; i <= n ; i++) {
            builder.delete(0,builder.length());
            currentChar = ans.charAt(0);
            count = 0;
            for (char c : ans.toCharArray()) {
                if (c == currentChar) count++;
                else {
                    builder.append(count);
                    builder.append(currentChar);
                    count=1;
                    currentChar=c;
                }
            }
            builder.append(count);
            builder.append(currentChar);
            ans = builder.toString();
        }
        return ans;
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while (left <= right){
            mid = left+(right-left)/2; //防止溢出；
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] < target){
                left = mid +1;
            }else {
                right = mid -1;
            }
        }
        return left;
    }
//    public int searchInsert(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] >= target) return i;
//        }
//        return nums.length;
//    }

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null ) return 0;
        if (needle.trim().equals("")) return 0;
        if (haystack.trim().equals("")) return -1;
        char n = needle.charAt(0);
        int j =0;
        for (int i = 0; i < haystack.length(); i++) {
            char c = haystack.charAt(i);
            if (c == n && i+needle.length()<haystack.length()){
                for ( j = 0; j < needle.length(); j++) {
                    if ( haystack.charAt(i+j) != needle.charAt(j)){
                         break;
                    }
                }
                if (j == needle.length()) return i;
            }
        }
        return -1;
    }

    public int removeElement(int[] nums, int val) {
        int index = -1; //初值优化
        int find = 0;
        while (find<nums.length){
            if (nums[find] != val){
                nums[++index] = nums[find];
            }
            find++;
        }
        return index+1;
    }

    public int removeDuplicates(int[] nums) {  //待提高效率
        int count = 1;
        int find = 1;
        while (find < nums.length){
            while (find < nums.length && nums[find] == nums[find - 1]) {
                find++;
            }
         }
        return count;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null ) return null;
        if (head.next == null) return head;

        ListNode temp = head.next;
    //    head.next = head.next.next;
        temp.next = head;
        ListNode node = swapPairs(head.next);
        head.next = node;
        return temp;
    }

    public static List<String> generateParenthesis(int n) {
  //      ArrayList<String> ans = new ArrayList<>();
        ArrayList<List<String>> lists = new ArrayList<>();

        String str  = new String(""); // 0
        List<String> strs = new ArrayList<>();
        strs.add(str);
        lists.add(strs);

        str = new String("()"); // !1
        strs = new ArrayList<>();
        strs.add(str);
        lists.add(strs);

        for (int i = 2; i <= n ; i++) {
            strs = new ArrayList<>();
            for (int j = 0; j <= i-1; j++) {
                List<String> strs_1 = lists.get(j);
                List<String> strs_2 = lists.get(i-1-j);
                for (String str_1 : strs_1) {
                    for (String str_2 : strs_2) {
                        str = new String();
                        str = "(" + str_1 + ")" + str_2;
                        strs.add(str);
                    }
                }
            }
            lists.add(strs);
        }
        return  strs  = lists.get(lists.size()-1);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if ( l1 == null ) return l2;
        if ( l2 == null ) return l1;
        ListNode newHead = null ,node = null;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                if (newHead == null){
                    newHead = l1;
                    node = newHead;
                    l1 = l1.next;
                }else {
                    node.next = l1;
                    node=node.next;
                    l1 = l1.next;
                }
            }else {
                if (newHead == null){
                    newHead = l2;
                    node = newHead;
                    l2 = l2.next;
                }else {
                    node.next = l2;
                    node=node.next;
                    l2 = l2.next;
                }
            }
        }
        if (l1 != null) node.next = l1;
        if (l2 != null) node.next = l2;
        return newHead;
    }

    public boolean isValid(String s) {
        if (s == null || s.trim().equals("")){
            return true;
        }
        Stack<Character> stack = new Stack<>();
        char c;
        for (int i = 0; i < s.length(); i++) {
             c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
                continue;
            }
            if (!stack.empty()) {
                char pop = stack.pop().charValue();
                switch (c) {
                    case ')':
                        if (pop == '(') break;
                        else return false;
                    case '}':
                        if (pop == '{') break;
                        else return false;
                    case ']':
                        if (pop == '[') break;
                        else return false;
                }
            }else {  //栈为空但是}】）进入
               return false;
            }
        }
        if (stack.empty()) return true;
        else return false;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null ) return head;
        if (head.next == null && n == 1 ) return null; //如果只有一个节点；
        ListNode currentNode = head;
        ListNode targetNode = head;
        int count = 0;

        while (currentNode.next!= null && n>0) {
            currentNode = currentNode.next;
            n--;
        }
        while (currentNode.next != null){

            targetNode = targetNode.next;
            currentNode = currentNode.next;
        }
        if (n <= 0) {
            targetNode.next = targetNode.next.next;
        }else {
            return head.next;
        }
        return  head;
    }


    public static  class ListNode {
      int val;
     ListNode next;
      ListNode(int x) { val = x; }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>() ;
        Arrays.sort(nums);
        if (nums == null || nums.length <4 ) return ans;
        int R,L,sumOf2,sum,legth=nums.length;
        for (int i = 0; i < nums.length - 3; i++) {
            if (i !=0 && nums[i] == nums[i-1]) continue;
            if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] >target) break;
            if (nums[i] + nums[legth-1] + nums[legth-2] + nums[legth-3] < target) continue;
            for (int j = i+1; j < nums.length -2 ; j++) {
                if (j !=i+1 && nums[j] == nums[j-1]) continue;
                if (nums[i] + nums[j] + nums[j+1] + nums[j+2] >target) break;
                if (nums[i] + nums[j] + nums[legth-1] + nums[legth-2] < target) continue;
                sumOf2 = nums[i] + nums[j];
                L=j+1;
                R=nums.length-1;
                while (L < R) {
                    sum = sumOf2 + nums[L] + nums[R];
                    if (sum > target) {
                        do {
                            R--;
                        }while (R>L && nums[R] == nums[R+1]);  //减少完之后发现与之前的一样；
                    } else if (target > sum) {
                        do{
                            L++;
                        }while (L<R && nums[L] == nums[L-1]);
                    } else {
                        ArrayList<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]);
                        integers.add(nums[j]);
                        integers.add(nums[L]);
                        integers.add(nums[R]);
                        ans.add(integers);
                        do {
                            R--;
                        }while (R>L && nums[R] == nums[R+1]);  //减少完之后发现与之前的一样；
                        do{
                            L++;
                        }while (L<R && nums[L] == nums[L-1]);
                    };
                }
            }
        }
        return ans;
    }

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        StringBuilder builder = new StringBuilder();
        if (digits == null || digits.trim().equals("")) return ans;
        digits = digits.trim();
        char[][] c = {{'a','b','c'},{'d','e','f'},{'g','h','i'},
                      {'g','k','l'},{'m','n','o'},{'p','q','r','s'},
                      {'t','u','v'},{'w','x','y','z'}};
        helper(digits,c,0,builder,ans);
        return ans;
    }
    public void helper(String digits, char[][] c, int index, StringBuilder builder, List<String> ans){
        if (index >= digits.length()) {
            ans.add(builder.toString());
            return;
        }
        char digit = digits.charAt(index);
        int dig = digit-'2';
        for (int i = 0; i < c[dig].length; i++) {
            builder.append(c[dig][i]);
            helper(digits,c,index+1,builder,ans);
            builder.deleteCharAt(builder.length()-1);
        }
    }

    public static int threeSumClosest(int[] nums, int target) {
        int ans = target ;
        int minRange = Integer.MAX_VALUE ;
        Arrays.sort(nums);
        if (nums == null || nums.length <3 ) return ans;
        int R,L,sum;
        for (int i = 0; i < nums.length - 2; i++) {
            if (i !=0 && nums[i] == nums[i-1]) continue;
            L=i+1;
            R=nums.length-1;
            while (L < R) {
                sum = nums[i] + nums[L] + nums[R];
                if (sum > target) {
                    R--;
                    if (sum - target < minRange) {
                        ans = sum;
                        minRange = sum - target;
                    }
                } else if (target > sum) {
                    L++;
                    if (target - sum < minRange) {
                        ans = sum;
                        minRange = target - sum;
                    }
                } else return target;
            }
        }
        return ans;
    }
        public static List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<>();
        if (nums.length <3 )  return list;
        Arrays.sort(nums);
        int temp = 0;
        int start = 0,end = nums.length-1,mid = 0;
//        int lastMax = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] >0) break;
            if (i != 0 && nums[i] == nums[i-1]) continue; //去重。
            for (int j = i+1; j < nums.length - 1; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) continue;
                temp = nums[i] + nums[j];
                start = j+1;
                end= nums.length -1;
                if (nums[end] == -temp){   //防止要找的数一开始就在end位置。
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.add(nums[i]);
                    integers.add(nums[j]);
                    integers.add(nums[end]);
                    list.add(integers);
                    continue;
                }
                while (start < end){   //二分法进行查找 //其实二分法查找，首先可以排除开头和结尾的两个数字。
                    mid = (start + end)/2;
                    if (nums[mid] == -temp){
                        ArrayList<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]);
                        integers.add(nums[j]);
                        integers.add(nums[mid]);
                        list.add(integers);
                        break;
                    }else if( nums[mid] > - temp )
                        end = mid-1;
                    else start = mid +1;
                }

            }
        }
        return list;
    }
//    public List<List<Integer>> threeSum(int[] nums) {
//        ArrayList<List<Integer>> list = new ArrayList<>();
//        if (nums.length <3 )  return list;
//        int temp = 0;
//        for (int i = 0; i < nums.length - 2; i++) {
//            for (int j = i+1; j < nums.length - 1; j++) {
//                temp = nums[i] + nums[j];
//                for (int k = j+1; k < nums.length; k++) {
//                    if (nums[k]+temp == 0){
//                        ArrayList<Integer> integers = new ArrayList<>();
//                         integers.add(nums[i]);
//                        integers.add(nums[j]);
//                        integers.add(nums[k]);
//                        list.add(integers);
//                    }
//                }
//            }
//        }
//        return list;
//    }
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        StringBuilder builder = new StringBuilder("");
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            int j = 1;
            for (; j < strs.length; j++) {
                if (strs[j].length() <= i) break;  //注意判断。
                if ( c != strs[j].charAt(i)) break;
            }
            if ( j < strs.length) break;
            else builder.append(c);
        }
        return builder.toString();
    }
    public int romanToInt(String s) {
          int res = 0;
          int index = 0;
          int preValue = 0;
          while (index <s.length()){
              char c = s.charAt(index);
              int value = getValue(c);
              if (value > preValue){
                  value = value - 2*preValue;
              }
              res+=value;
              index++;
          }
        return res;
    }
    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
    public String intToRoman(int num) {
        char[] arr = {'I','X','C','M'};
        char[] arr_2 = {'V','L','D'};
        int index = 0;
        int temp = 0;
        StringBuilder builder = new StringBuilder();
        while (num != 0){
            temp = num%10;
            if (temp <= 3){
               while (temp > 0){
                   builder.append(arr[index]);
                   temp--;
               }
            }else if (temp == 4) {
                 builder.append(arr_2[index]);
                 builder.append(arr[index]);
            }else if (temp <9){
                while (temp-5>0) {
                    builder.append(arr[index]);
                    temp--;
                }
                builder.append(arr_2[index]);

            }else {
                builder.append(arr[index + 1]);
                builder.append(arr[index]);
            }
            num /= 10;
            index ++;
        }
        return builder.reverse().toString();
  }
    public int maxArea(int[] height) {
        int start = 0;
        int end = height.length-1;
        int maxArea = 0;
        int temp = 0;
        while (start != end){
            temp = Math.min(height[start],height[end])*(end - start);
            if (temp > maxArea) maxArea = temp;
            if(height[start] > height[end]) end--;
            else start++;
        }
        return  maxArea;

    }
    //. * 立即匹配，字母延迟匹配
    // 待完成。
    public static  boolean isMatch(String s, String p) {
        if (p.trim().equals("")){
            if (s.trim().equals("")) return true;
            else return false;
        }
        if (s.trim().equals("")) return true;
        int indexS = 0;
        int indexP = 0;
        char lastP = p.charAt(0);
        boolean isLastSMatch = true;
     //   Stack<Character> stack = new Stack<>();
        while(indexS < s.length() && indexP < p.length()){
            char c = p.charAt(indexP);
            if(c == '.') {
//                while (! stack.empty()){
//                    char c1 = stack.pop().charValue();
//                    if (c1 == s.charAt(indexS)){
//                        indexS++;
//                    }else return  false;
//                }
                if (!isLastSMatch){
                    if (lastP == s.charAt(indexS)) indexS++;
                    else return false;
                }
                indexS++;
                isLastSMatch = true;
                lastP = '.';
            }
            if(c == '*'){
                if (!isLastSMatch){

                }else {
                    if (lastP == '.') return true;
                    while (indexS <s.length() && s.charAt(indexS) == lastP)
                        indexS++;
                }

                isLastSMatch = true;
                lastP = '*';
            }
            if (c  <= 'z' && c>='a'){
                if (!isLastSMatch){
                    if (s.charAt(indexS) != c)  return false;
                }else {
                    if (s.charAt(indexS) == c){
                        indexS++;
                        isLastSMatch = true;
                        lastP=c;
                    }
                    else {
                        isLastSMatch = false;
                        lastP = c;
                    }
                }
            }
            indexP++;
        }
        if(indexS == s.length()) return true;
        else return false;
    }

    public static   boolean isPalindrome(int x) {
        if(x<0 ) return false;
        if(x == 0) return true;
        if (x%10 == 0) return false; //简化后面的判断
        int temp = 0;
        int lastX = x;
        while(x != 0 ){
            temp = temp * 10 + x%10;
            lastX = x; //保存上一次X的值，用于奇数位情况下；
            x/=10;
            if (x == temp) return true;
            else if (temp > x){
                if (temp == lastX) return true; //奇数位情况下
                return false;
            }
        }
        return  false;
    }
    public static int reverse(int x) {
        long result = 0L;
        while (x!=0){
            result=result*10+x%10;
            x/=10;
        }
        if(result> Integer.MAX_VALUE) return  Integer.MAX_VALUE;
        else if (result< Integer.MIN_VALUE) return Integer.MIN_VALUE;
        else return (int)result;
    }
    public static int myAtoi(String str) {
        str = str.trim();
        if(str.equals("")) return 0;
        long result=0;  //防止溢出
        int fuhao=1;
        int index=1;
        char c = str.charAt(0);
        if(c == '+') ;
        else if(c == '-') fuhao = -1;
        else if(c<='9' && c>='0') result = c-'0';
        else return 0;

            while (index<str.length() && str.charAt(index) <='9' && str.charAt(index) >='0'){
                result=result*10+(str.charAt(index)-'0')*fuhao;
                index ++;
                if(result> Integer.MAX_VALUE ) {
                    result = Integer.MAX_VALUE;
                    break;
                }
                else if(result< Integer.MIN_VALUE) {
                    result = Integer.MIN_VALUE;
                    break;
                }
            }
        return (int)result;
    }
}
